מבנה מילון:

• מבנה נתונים אבסטרקטי שמאחסן איברים, כאשר לכל איבר יש מפתח חד חד ערכי, שתומך ב:
  • פעולת Search(S,k): מחזיר את האיבר שהמפתח שלו זה k
  • פעולת Insert (S,x): מוסיף את x ל S
  • פעולת Delete(S,x): מסיר את x מ S
• טבלאות גיבוב (HashTable) הן מימוש של מבנה זה.

גיבוב (Hashing):

• הרעיון המרכזי:
  • במטרה לחסוך בזיכרון בבניית מערך עם מספר מפתחות גדול, משתמשים בפונקציית גיבוב (Hash function) כדי למפות את המפתחות למערך בעל טווח קטן בהרבה (בגודל m).
• התנגשויות (Collisions):
  • מצב בלתי נמנע בו שני מפתחות או יותר ממופים לאותו אינדקס בדיוק.

פתרון ההתנגשויות:

• בעזרת שרשור (Chaining):

  • הטבלה היא מערך של רשימות מקושרות. כל איבר שממופה לאינדקס מסוים מתווסף לרשימה באותו תא (מומלץ להכניס לראש הרשימה ב-Θ(1)).
  • זמני ריצה :
    • הכנסה: $\mathrm{\Theta }1$.
    • חיפוש: $\mathrm{\Theta }n$ (במקרה שכל האיברים הוגרלו לאותו התא בדיוק).
    • מחיקה: $\mathrm{\Theta }n$ ברשימה חד-כיוונית, אך ניתן לייעל ל $\mathrm{\Theta }1$ אם משתמשים ברשימה דו-כיוונית.
  • תוחלת זמן הריצה וניתוח (במקרה של מפתחות אקראיים):
    • מקביל לבעיית "כדורים לסלים" (Balls into bins) שבה זורקים n כדורים ל-m סלים.
    • מקדם העומס ($\alpha$):
      • מוגדר כיחס שבין מספר האיברים בטבלה (N) לגודל הטבלה (M)​.
      • תוחלת מספר האיברים שייפלו לכל תא היא $\alpha$.
      • תוחלת זמן החיפוש (זמן החיפוש הצפוי) היא $\mathrm{\Theta }(1+\alpha )$ (ה-1 מייצג את זמן הגישה הראשונית לתא, גם אם הוא ריק).

• בעזרת בחינה ליניארית (Linear Probing):

  • שיטה נוספת השייכת ל"מיעון פתוח" (Open Addressing), שבה לא משתמשים ברשימות מקושרות, אלא שומרים את כל האיברים ישירות בתאי המערך.
  • פעולות המבנה:
    • הכנסה: מנסים להכניס איבר ל- T(h(k)), כאשר h(k) = k mod 10. אם התא תפוס, מתקדמים לתא הבא אחריו (מודולו m) וכך הלאה עד שמוצאים תא פנוי (Null) ומכניסים אליו.
    • חיפוש: מתחילים מהתא T(h(k)). אם האיבר שם – מצוין. אם יש שם איבר אחר, ממשיכים לתא הבא. עוצרים רק אם מוצאים את האיבר או אם מגיעים לתא פנוי (Null), שאז ניתן להסיק שהאיבר אינו קיים בטבלה.
    • מחיקה: אי אפשר פשוט לכתוב Null בתא, כי זה יקטע את רצף החיפוש עבור איברים אחרים שהוכנסו אחריו. במקום זאת, יש שתי גישות:
      1. סימון DELETED: במקום למחוק, שמים סימון מיוחד. החיפוש מתעלם ממנו וממשיך, והכנסה יכולה לדרוס אותו. החיסרון הוא שזמן החיפוש מתחיל להיות מושפע גם מכמות האיברים המחוקים (העומס המדומה $\alpha$' יכול להיות גדול מ-$\alpha$), ולכן הטבלה תאט לאורך זמן.
      2. מחיקה והזזה: מוחקים את התא (הופכים ל-Null), ואז לוקחים את כל האיברים מהתאים הבאים ברצף (עד ה-Null הבא) ומכניסים אותם מחדש לטבלה כדי למנוע קטיעה של מסלולי חיפוש. שיטה זו שומרת על זמן חיפוש אופטימלי.

• הערות למקדם עומס: בשיטה זו מקדם העומס $\alpha$ חייב להיות ממש קטן מ-1 (למשל, $ϵ-1$), וברגע שמתקרבים אליו חובה לבצע Rehashing כדי לשמור על ביצועים תקינים.

פונקציות גיבוב אוניברסליות (Universal Hash Functions):

• במציאות, המפתחות המוזנים אינם בהכרח אקראיים, ולכן בחירת פונקציה קבועה עלולה להוביל לביצועים גרועים. במקום זאת, נשתמש במשפחה אוניברסלית של פונקציות.
• הרעיון המרכזי:
  • משפחת פונקציות תוגדר כ"אוניברסלית" אם לכל שני מפתחות שונים x,y, ההסתברות שפונקציה h שתיבחר באקראי מהמשפחה תמפה אותם לאותו התא חסומה על ידי $\frac{1}{m}$​.
  • כאשר בוחרים פונקציה ממשפחה זו בהגרלה אקראית בזמן יצירת הטבלה, מובטח שתוחלת אורך הרשימה בכל תא תהיה קטנה או שווה ל- $\alpha +1$, גם אם המפתחות עצמם אינם אקראיים.

גיבוב מחדש (Rehashing):

• על מנת לשמור על זמן החיפוש הקבוע, נרצה שמקדם העומס יישאר קטן.
• כאשר הטבלה מתמלאת, יוצרים טבלה חדשה וגדולה יותר.
• בוחרים פונקציית גיבוב חדשה מתוך המשפחה האוניברסלית, ומעתיקים (ממפים מחדש) את כל איברי הטבלה הישנה לטבלה החדשה.
• סיבוכיות:
  • פעולת הגיבוב מחדש עולה $\mathrm{\Theta }n$ במקרה הגרוע, אך בתוחלת ההכנסות מתאזנות ל - $\mathrm{\Theta }1$ צפוי.

תובנות מהתרגול:

• כאשר פותרים באמצעות טבלת גיבוב, ישנם 3 משפטים שצריכים להיכנס בהסבר:
  • "נשתמש בטבלת גיבוב על בסיס ---- " (כאשר לרוב היא תהיה מבוססת שרשור).
  • "נגדיר טבלה בגודל N בזמן $\mathrm{\Theta }(N)$ גרוע ביותר"
  • "נבחר באקראי פונקציית גיבוב מתוך משפחת פונקציות אוניברסלית (ולהוסיף מהי המשפחה)"
• במבני נתונים מבוססים הסתברות, צריך לומר על זמן ריצה מסוים שהוא זמן הריצה הצפוי.

אלגוריתם Bloom FIlter (מתוך הרצאה 13):

• מהווה מימוש לבדיקה אם דף אינטרנט מסוים הוא זדוני או לא באמצעות טבלאות גיבוב.

• כדי לקבל מימוש מהיר, נצטרך להקריב את היכולת להגיד אם תמיד בהכרח הדף הוא טוב או רע. נוכל להגיד כשהוא רע, אבל לא תמיד כשהוא טוב, יהיה טוב ומצב ביניים "חשוד", ואת החשוד נצליב מול טבלת הרעים.

• נשמור מערך בגודל A כאשר כל הערכים בו הם 0, נבחר מתודת גיבוב, ונגדיר שהערכים עבור אינדקסים מסוימים הם 1, כאשר האינדקסים בהם נבחר הם הערכים של סט S המכיל את האתרים הרעים. כך כשנשלוף אינדקס מסוים נדע בוודאות אם האתר לא ברשימה (יחזיר 0) או שהוא אולי ברשימה (מכיוון שפעולת ההכנסה היא מודולו 10 של המספר לדוגמא אז אם 15 בתוך S ו25 לא, הם שניהם יהיו באינדקס חמש).

• נרצה שההסתברות שתא מסוים חשוד תהיה כמה שיותר קטנה. כדי להוריד אותה נגדיר שבמקום בפונקציית גיבוב אחת, נשתמש ב - t פונקציות גיבוב שונות, אשר משנות t ביטים ל1 במקום רק 1, וה bloom filter יחזיר שחשוד רק אם כל t התאים יהיו שווים ל - 1

• הערך האופטימלי ל t הוא בערך m/n כפול ln2